package com.demo.app.sort;


/**
 * @program: couple-game
 * @description: 两个有序链表合并为一条有序链表
 * @author: fbl
 * @create: 2025-05-16 10:19
 **/
public class LinkMerge {

    public static void main(String[] args) {
        Node n1 = new Node(1);
        n1.next = new Node(6);
        Node n2 = new Node(5);
        Node node = mergeNode(n1, n2);
        System.out.println(node);
    }

    private static Node mergeNode(Node n1, Node n2) {
        // 处理边界问题
        if (n1 == null || n2 == null) {
            return n1 == null ? n2 : n1;
        }
        // 找到总头 两个链条最小的那个头
        Node head = n1.getValue() >= n2.getValue() ? n2 : n1;
        // pre指针永远指向小的那个值
        Node pre = head;
        // cur1 cur2 俩指针相互比对，谁小谁往后挪
        Node cur1 = head.next;
        Node cur2 = head == n1 ? n2 : n1;
        while (cur1 != null && cur2 != null) {
            if(cur1.value >= cur2.value){
                pre.next = cur2;
                cur2 = cur2.next;
            }else{
                pre.next = cur1;
                cur1 = cur1.next;
            }
            pre = pre.next;
        }
        // 跳出循环，说明有一条链条走到头了，直接判断谁走到头了，然后指针指向另一条链条的头
        pre.next = cur1 == null ? cur2 : cur1;
        return head;
    }
}
